package org.getOffer;

/**
 * @Author yu
 * @Date 2021/7/5
 */
public class Practice10 {

    public static void main(String[] args) {
        Practice10 practice10=new Practice10();
        System.out.println(practice10.numWays(44));
        System.out.println(practice10.numWays2(44));

    }

    public static int flag = 1;

    public int numWays(int n) {

        //解法超时：
        if (n==0){
            return 1;
        }

        if (n==1){
            return 1;
        }

        return numWays(n-1)+numWays(n-2);

    }

    public int numWays2(int n){
        int i=1,j=1,sum=0;

        for (int m=0;m<n;m++){
            sum=(i+j)%1000000007;
            i=j;
            j=sum;
        }
        return i;
    }

}
